package com.zzy.algorithm.linkedList;

import com.zzy.algorithm.model.ListNode;

/**
 * LeetCode - 234 : 回文链表
 *
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 */
public class Q14_PalindromeLinkedList {

    public static void main(String[] args) {
        Q14_PalindromeLinkedList q14_palindromeLinkedList = new Q14_PalindromeLinkedList();
        boolean flag = q14_palindromeLinkedList.solution(ListNode.list6);
        System.out.println("flag = " + flag);
    }

    private boolean solution(ListNode head){
        // 找到中间节点
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        if(fast != null){
            slow = slow.next;
        }
        // 链表反转
        ListNode reverseNode = reverseLinkedNode(slow);
        // 对比
        while (reverseNode != null){
            if(reverseNode.val != head.val){
                return false;
            }
            reverseNode = reverseNode.next;
            head = head.next;
        }
        return true;
    }

    private ListNode reverseLinkedNode(ListNode middleNode) {
        if(middleNode == null || middleNode.next == null){
            return middleNode;
        }
        ListNode node = reverseLinkedNode(middleNode.next);
        middleNode.next.next = middleNode;
        middleNode.next = null;
        return node;
    }



}
